package graph;

import java.util.Arrays;
import java.util.Comparator;

public class Test {
    public static void main1(String[] args) {
        GraphByMatrix graph = new GraphByMatrix(4, true);
        char[] array = {'A', 'B', 'C', 'D'};
        graph.initArrayV(array);
        graph.addEdge('A', 'B', 1);
        graph.addEdge('A', 'D', 1);
        graph.addEdge('B', 'A', 1);
        graph.addEdge('B', 'C', 1);
        graph.addEdge('C', 'B', 1);
        graph.addEdge('C', 'D', 1);
        graph.addEdge('D', 'A', 1);
        graph.addEdge('D', 'C', 1);
        System.out.println(graph.getDevOfV('A'));
        graph.printGraph();
        System.out.println("bfs:");
        graph.bfs('A');
        System.out.println();
        System.out.println("dfs:");
        graph.dfs('A', new boolean[array.length]);
    }

    public static void main2(String[] args) {
        String str = "abcdefghi";
        char[] array = str.toCharArray();
        GraphByMatrix g = new GraphByMatrix(str.length(), false);
        g.initArrayV(array);
        g.addEdge('a', 'b', 4);
        g.addEdge('a', 'h', 8);
//g.addEdge('a', 'h', 9);
        g.addEdge('b', 'c', 8);
        g.addEdge('b', 'h', 11);
        g.addEdge('c', 'i', 2);
        g.addEdge('c', 'f', 4);
        g.addEdge('c', 'd', 7);
        g.addEdge('d', 'f', 14);
        g.addEdge('d', 'e', 9);
        g.addEdge('e', 'f', 10);
        g.addEdge('f', 'g', 2);
        g.addEdge('g', 'h', 1);
        g.addEdge('g', 'i', 6);
        g.addEdge('h', 'i', 7);
        GraphByMatrix kminTree = new GraphByMatrix(str.length(), false);
        kminTree.initArrayV(array);
        System.out.println(g.kruskal(kminTree));
        kminTree.printGraphKruskal();
    }

//    public static void main(String[] args) {
//        String str = "abcdefghi";
//        char[] array =str.toCharArray();
//        GraphByMatrix g = new GraphByMatrix(str.length(),false);
//        g.initArrayV(array);
//        g.addEdge('a', 'b', 4);
//        g.addEdge('a', 'h', 8);
////g.addEdge('a', 'h', 9);
//        g.addEdge('b', 'c', 8);
//        g.addEdge('b', 'h', 11);
//        g.addEdge('c', 'i', 2);
//        g.addEdge('c', 'f', 4);
//        g.addEdge('c', 'd', 7);
//        g.addEdge('d', 'f', 14);
//        g.addEdge('d', 'e', 9);
//        g.addEdge('e', 'f', 10);
//        g.addEdge('f', 'g', 2);
//        g.addEdge('g', 'h', 1);
//        g.addEdge('g', 'i', 6);
//        g.addEdge('h', 'i', 7);
//        GraphByMatrix primTree = new GraphByMatrix(str.length(),false);
//        primTree.initArrayV(array);
//        System.out.println(g.prim(primTree,'a'));
//        primTree.printGraph();
//    }

//    public static void main(String[] args) {
//        String str = "syztx";
//        char[] array = str.toCharArray();
//        GraphByMatrix g = new GraphByMatrix(str.length(),true);
//        g.initArrayV(array);
//        g.addEdge('s', 't', 10);
//        g.addEdge('s', 'y', 5);
//        g.addEdge('y', 't', 3);
//        g.addEdge('y', 'x', 9);
//        g.addEdge('y', 'z', 2);
//        g.addEdge('z', 's', 7);
//        g.addEdge('z', 'x', 6);
//        g.addEdge('t', 'y', 2);
//        g.addEdge('t', 'x', 1);
//        g.addEdge('x', 'z', 4);
//        /*
//搞不定负权值
//String str = "sytx";
//char[] array = str.toCharArray();
//GraphByMatrix g = new GraphByMatrix(str.length(),true);
//g.initArrayV(array);
//g.addEdge('s', 't', 10);
//g.addEdge('s', 'y', 5);
//g.addEdge('t', 'y', -7);
//g.addEdge('y', 'x', 3);*/
//        int[] dist = new int[array.length];
//        int[] parentPath = new int[array.length];
//        g.dijkstra('s', dist, parentPath);
//        g.printShortPath('s', dist, parentPath);
//
//        Integer[] a = new Integer[]{1,2,3,4,5};
//
//        Arrays.sort(a,(i,j) -> j - i);
//    }

//    public static void main(String[] args) {
//        String str = "syztx";
//        char[] array = str.toCharArray();
//        GraphByMatrix g = new GraphByMatrix(str.length(), true);
//        g.initArrayV(array);
////        g.addEdge('s', 't', 6);
////        g.addEdge('s', 'y', 7);
////        g.addEdge('y', 'z', 9);
////        g.addEdge('y', 'x', -3);
////        g.addEdge('z', 's', 2);
////        g.addEdge('z', 'x', 7);
////        g.addEdge('t', 'x', 5);
////        g.addEdge('t', 'y', 8);
////        g.addEdge('t', 'z', -4);
////        g.addEdge('x', 't', -2);
////负权回路实例
//        g.addEdge('s', 't', 6);
//        g.addEdge('s', 'y', 7);
//        g.addEdge('y', 'z', 9);
//        g.addEdge('y', 'x', -3);
//        g.addEdge('y', 's', 1);
//        g.addEdge('z', 's', 2);
//        g.addEdge('z', 'x', 7);
//        g.addEdge('t', 'x', 5);
//        g.addEdge('t', 'y', -8);
//        g.addEdge('t', 'z', -4);
//        g.addEdge('x', 't', -2);
//
//        int[] dist = new int[array.length];
//        int[] parentPath = new int[array.length];
//        boolean ﬂg = g.bellmanFord('s', dist, parentPath);
//        if (ﬂg) {
//            g.printShortPath('s', dist, parentPath);
//        } else {
//            System.out.println("存在负权回路");
//        }
//    }


    public static void main(String[] args) {
        String str = "12345";
        char[] array = str.toCharArray();
        GraphByMatrix g = new GraphByMatrix(str.length(),true);
        g.initArrayV(array);
        g.addEdge('1', '2', 3);
        g.addEdge('1', '3', 8);
        g.addEdge('1', '5', -4);
        g.addEdge('2', '4', 1);
        g.addEdge('2', '5', 7);
        g.addEdge('3', '2', 4);
        g.addEdge('4', '1', 2);
        g.addEdge('4', '3', -5);
        g.addEdge('5', '4', 6);
        int[][] dist = new int[array.length][array.length];
        int[][] parentPath = new int[array.length][array.length];
        g.ﬂoydWarShall(dist,parentPath);

        for (int i = 0; i < array.length; i++) {
            g.printShortPath(array[i],dist[i],parentPath[i]);
            System.out.println("**********************");
        }
    }
}
